分享人:杨纲
目录
1.背景介绍
2.知识剖析
3.常见问题
4.解决方案
5.编码实战
6.扩展思考
7.参考文献
8.更多讨论
洗牌算法(Shuffling Algorithm),顾名思义,它的产生是用来解决类似洗牌这种场景的问题的,目的是产生一串等概率的随机列,使得很难去预测牌的顺序。
现在的各种牌类游戏都有自己的洗牌算法,为了保证游戏的趣味性,各自的实现中都有自己考虑的因素添加在其中。 1999年,一个很流行的在线扑克平台的开发者开发的洗牌软件,带有很微小但很致命的漏洞,导致了灾难性的结果。 黑客只要知道手中的两张牌和3张公用牌,就可以猜出转牌和河牌时会来什么牌,以及其他玩家的牌。
洗牌算法的应用也很广,比如三国杀游戏、斗地主游戏等等。讲一个最常见的场景,就是播放器的随机播放。 有些播放器的随机播放,是每次产生一个随机数来选择播放的歌曲,这样就有可能还没有听完所有的歌前,又听到已经听过的歌。 另一种就是利用洗牌算法,把待播放的歌曲列表shuffle。 如何判断使用的是哪一种方案呢? 很简单,如果点上一首还能回去,则利用的是洗牌算法,如果点上一首又是另外一首歌,则说明使用的是随机产生方法。
其算法思想就是 从原始数组中随机抽取一个新的元素到新数组中
每次从未处理的数组中随机取一个元素,然后把该元素放到数组的尾部,即数组的尾部放的就是已经处理过的元素,这是一种原地打乱的算法,每个元素随机概率也相等,时间复杂度从 Fisher 算法的 O(n2)提升到了 O(n)
Knuth-Durstenfeld Shuffle 是一个in-place算法,原始数据被直接打乱,有些应用中可能需要保留原始数据,因此需要开辟一个新数组来存储打乱后的序列。 Inside-Out Algorithm 算法的基本思想是设一游标i从前向后扫描原始数据的拷贝,在[0, i]之间随机一个下标j,然后用位置j的元素替换掉位置i的数字,再用原始数据位置i的元素替换掉拷贝数据位置j的元素。其作用相当于在拷贝数据中交换i与j位置处的值。
Fisher–Yates Shuffle是如何实现的?
Array.prototype.shuffle = function() {
var input = this;
for (var i = input.length - 1; i >= 0; i--) {
var randomIndex = Math.floor(Math.random() * (i + 1));//获取小于this.length的随机整数
var itemAtIndex = input[randomIndex];
input[randomIndex] = input[i];
input[i] = itemAtIndex;//input[randomIndex]和input[i]交换值
}
return input;
}
shuffle 函数挂载在 Array 对象的原型之下,便于数组直接调用该函数。在 shuffle 函数内部,this 引用的就是调用该 shuffle 的数组。 用一个新的变量引用 this,也就是调用 shuffle 函数的数组。接下来的for循环用于遍历所有数组内的所有元素,并进行随机交换。 注意,遍历顺序是从后往前进行的,也就是说从 input.length-1 位置的元素开始,直到遍历到数组中的第一个元素。遍历过程中的位置由变量 i 指定。 接下来,使用了两行代码在指定范围内挑选一个随机元素。 变量randomIndex存储了一个随机数,该随机数可以用作数组的索引,进而提取一个随机元素。注意,该随机数的最大值并不是数组的长度,而是变量i的值。 确定了随机元素的索引之后,用新的变量保存该元素的值,然后交换选中元素和随机元素的值。
笔者目前了解到最优秀的是梅森旋转算法,其在低于623次元的空间以内不存在线性回归,但仍然是一个伪随机算法。
参考一:洗牌算法怎样才够乱
参考三: 当随机不够随机:一个在线扑克游戏的教训
参考四: 随机问题之--洗牌算法
还有没有更简单的洗牌算法
BY ︱王奎智︱杨纲